上篇文章我们介绍了密码学的基础，相信你已经对密码学及相关的知识有所了解，如果还没有阅读过，可以点击这里查看👉 RSA加密(一) 密码学基础 。
这篇文章主要给大家讲解下RSA加密的过程，但在讲加密过程前我们需要了解几个数学公式。都很简单，相信大家看了就会明白，文中遇到有链接的地方，可先跳过不影响阅读。下面我们先来看看RSA加密的介绍。
RSA加密简介
本文开篇的这张图就是RSA加密的三位作者，RSA算法是由Rivest、Shamir和Adleman在1977年共同提出，他们当时正好都在麻省理工学院工作，RSA就是他们三人姓氏开头字母拼在一起组成的。
但其实在RSA算法提出的4年前的1973年，在英国政府通讯总部工作的数学家克利福德·柯克斯（Clifford Cocks）在一个内部文件中便提出了一个与之等效的算法，但该算法当时被列入机密，直到1997年才得到公开（稍微有一些些可惜了~）。
从上篇文章我们了解到，RSA加密算法是通过分解质因数的困难性来实现的。换言之，对一个极大整数做因数分解愈困难，RSA算法愈可靠。假如有人找到一种快速因数分解的算法的话，那么用RSA加密的信息的可靠性就会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的RSA钥匙才可能被强力方式破解。到当前为止，世界上还没有任何可靠的攻击RSA算法的方式。只要其钥匙的长度足够长，用RSA加密的信息实际上是不能被破解的，正因为RSA加密的安全性，所以RSA加密算法在当今互联网信息传递中被广泛的使用。
可以毫不夸张的说：只要有计算机网络的地方就有RSA加密算法。
数学公式
前面说到要理解RSA加密需要先了解一些数论相关的知识，这里我总结了几个必要的公式，方便后面能够更好的理解加密过程。
1.互质关系
- 质数定义：除了1和它本身，不能被其它数整除的数。例如：2、3、5、7、11、13、17、19、23、29…
- 任意两个质数构成互质关系。例如5和7，除1之外没有其他数能够整除5和7。
- 质数A与不是它的倍数的数构成互质。例如5能和1、2、3、4、6、7、8、9、11构成互质关系。
2.欧拉函数
对于任意正整数n，欧拉函数就是计算比n小的数中与n互质的数有多少个，用φ(n)表示，例：
计算整数8的欧拉函数：与8形成互质关系的是1、3、5、7共四个数，所以 φ(8) = 4。
从上面互质关系中的第三条我们可以知道，当n是一个质数时，比n小的所有数都与n形成互质关系，所以有：
n是质数：φ(n) = n-1
根据中国剩余定理(又称孙子定理)我们可以得到：两个互质整数p、q乘积的欧拉函数为：
φ(pxq) = φ(p)φ(q) （即可分开计算再相乘）
所以当p、q都是质数的时候，根据上面的公式 φ(n)=n-1 我们可以得到：
φ(pxq)=(p-1)(q-1)
我们知道上面这种情况的欧拉公式就够了，关于更多欧拉函数的相关知识我们可以查看👉这里
3.欧拉定理
介绍欧拉定理之前，先说下取余操作。大家都知道 5除4余1，在数学中表示为 5=1(mod4) ，因为在计算机中计算余数的符号为百分号%，所以下面公式统一用 5%4=1 这种既简洁又好理解的形式表示。
欧拉定理：若正整数a和n互质则有
$a^{φ(n)}$ % n=1
正如上面的式子，伟大的定理往往都相当简洁！关于欧拉定理如何证明，感兴趣的同学可以查看👉这里
另外与之相关的一个概念，若正整数a和n互质则存在整数b使得：
ab % n=1
b就叫做a的模反元素，那b就一定存在吗？欧拉定理我们可以写成:
a x $a^{φ(n)-1}$ % n=1
所以b=$a^{φ(n)-1}$时上式成立，故b必然存在。
对于后面的加解密过程，我们主要用到如下两个公式：
RSA加密、解密过程
生成公钥、私钥
1. 随机找出两个不相等的质数 p、q
这里方便起见我们取 p=5，q=11（实际应用中p和q越大越难破解）
2. 计算p、q的乘积 n = p x q
n = 5 x 11 = 55（n的二进制长度称为RSA加密的密钥长度，这里55表示成二进制是110111，长度只有6位，实际应用中为1024位或更高的2048位）
3. 计算n的欧拉函数φ(n)，根据上面我们所推导的欧拉函数，得到：φ(n)=(p-1)(q-1)
φ(n) = 4 x 10 = 40
4. 随机选择一个整数e，条件是1< e < φ(n)，且e与φ(n) 互质。
e和40要互质，为了方便这里我们取 e = 3.（ 实际应用中这里一般取65537 ）
5. 计算e对于φ(n)的模反元素d
即 ed % φ(n)=1可以写成：3d = k40+1，当k=2时，我们得到d=27.
6. 将e和n封装作为公钥(e,n)，d和n封装作为私钥(d,n)，即：
公钥：（e=3，n=55）
私钥：（d=27，n=55）
加密
上面我们已经计算出了公钥和私钥，根据上篇文章中的非对称加密流程。发送发收到公钥后开始进行加密操作。
假设现在我们要发送一段消息m=4，公钥为 (e=3,n=55)
m必须是一个整数（可将发送的消息通过ASCII码转换成十进制），且m<n，这就导致RSA加密的内容长度受到了限制。
计算密文：c = $m^e$ % n
即密文c = $ 4^3$ % 55 = 64%55 = 9
发送方便将密文9，通过网络等途径发送给接收方。
解密
接收方收到密文c=9后，使用自己创建的私钥 (d=27,n=55) 进行解密操作。
计算原文：m = $c^d$ % n
即原文m = $9^{27}$ % 55 = 4 （简单推导见👉这里，也可通过编程验证）
于是接收方便得到了发送方想要发送的消息，整个加密和解密过程就结束了。
总结
可以看到RSA加密和解密的过程并不复杂，用到的公式也只有仅仅两个，但这里面还有一些问题等待着我们去探索，例如：
- m<n，这就导致RSA加密的内容长度受到了限制，那如何加密发送一段很长的文本呢？
- RSA在公钥和密文传输的过程中就真的很安全吗？
- 为什么解密的时候原文：m 就等于 $c^d$ % n呢？
欢迎在留言区说出你的想法，我们将在下一篇文章中给大家带来解答。